#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>

#define ElemType char

typedef struct Node{
    ElemType character;
    int weight;
    int parent,left,right;
}HTNode,*HuffmanTree;   //哈夫曼树结构

typedef char **HuffmanCode; //动态内存分配huffman编码，二元数组指针

void Selection(HuffmanTree HT,int n,int* s1,int* s2);
void write_HuffmanTree(HuffmanTree HT,int n);  //将哈夫曼树以前序遍历的形式写入文件中
void Transform_Coding(HuffmanTree HT,int n);
void write_CodeFile(HuffmanCode HC,int n);
void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,const HTNode* w,int n);
void menu(){
    printf("Please input the char and weight(enter -1 to leave):");
}
//输入一系列的字符串，以及对应的权重
//编码还是按照原始来编码，那么在写入文件的时候，就是写入权值

int main(){
    int capacity=3;  //默认分配的数组空间
    int size=0;  //当前已用的数组空间
    HTNode* w = (HTNode*)malloc(capacity * sizeof(HTNode));  //分配默认空间
    if (w == NULL) {
        printf("%s", strerror(errno));
        exit(1);
    }
    int i=0;
    do {
        menu();
        scanf_s(" %c %d", &w[i].character, sizeof(w[i].character), &w[i].weight);

        size += 1;
        if (size == capacity) {  //如果数组空间不够，扩充一倍
            capacity *= 2;
            HTNode *temp = (HTNode*)realloc(w, capacity * sizeof(HTNode));
            if (temp == NULL) { // 如果重新分配失败，则直接退出程序
                printf("%s", strerror(errno));
                free(w); //释放之前已分配的内存
                exit(1);
            }
            w = temp;
        }

        i+=1;
    } while (w[i-1].character != '-');

    int n=size-1;

    HuffmanTree HT=NULL;
    HuffmanCode HC=NULL;
    HuffmanCoding(HT,HC,w,n);
    return 0;
}

void write_CodeFile(HuffmanCode HC,int n){
    FILE* file= fopen("CodeFile.txt","w");
    if(file==NULL){
        printf("%s\n", strerror(errno));  //若文件打开失败，打印出出问题的情况
        assert(file!=NULL);  //断言，进入这个循环则停止程序
    }
    int i;
    for(i=1;i<=n;i++){
        fprintf(file,"%s ",HC[i]);
    }
    fclose(file);
    file=NULL;
}

//将哈夫曼树以前序遍历的形式写入文件中
void write_HuffmanTree(HuffmanTree HT,int n){
    FILE* file= fopen("hfmTree.txt","w");
    if(file==NULL){
        printf("%s\n", strerror(errno));
        return;
    }
    //将HC中的写入文件中
    int i;
    fprintf(file,"%s\t%s\t%s\t%s\t%s\n","char","weight","parent","left","right");
    for(i=1;i<=2*n-1;i++){
        fprintf(file, "%-4c\t%-6d\t%-6d\t%-4d\t%-5d\n",HT[i].character,HT[i].weight,HT[i].parent,HT[i].left,HT[i].right);
    }
    fclose(file);
    file=NULL;
}

void Selection(HuffmanTree HT,int n,int* s1,int* s2){
    //找到HT[1...i-1]中parent为0且weight最小的两个结点
    int i;
    int a1,a2;    //用a来记住最小权重的位置
    a1=a2=-1;
    for(i=0;i<=n;i++){
        if(HT[i].parent==0){
            if(a1==-1||HT[i].weight<HT[a1].weight){   //只需要让a2记住上一个a1的位置即可
                a2=a1;
                a1=i;
            } else if(a2==-1||HT[i].weight<HT[a2].weight){
                a2=i;
            }
        }
    }
    *s1=a1;
    *s2=a2;
}

void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,const HTNode* w,int n){  //w存放n个字符的权值，n即字符数
    if(n<=1){
        printf("have not found the chars\n");
        return;
    }
    int m=2*n-1;   //哈夫曼树中的总结点个数
    HT=(HuffmanTree) malloc((m+1)* sizeof(HTNode));  //0号单元未用所以加一，（但实际上我加了二）
    if(HT==NULL){
        printf("%s\n", strerror(errno));
        return;
    }
    int i;
    HuffmanTree p;
    for (p=HT+1,i=1;i<=m;++p,++i) {    //哈夫曼数组初始化
        p->right=0;
        p->left=0;
        p->weight=0;
        p->parent=0;
        p->character='0';
    }
    for(p=HT+1,i=1;i<=n;++p,++i,++w){   //初始化权重
        p->weight=w->weight;
        p->character=w->character;
    }
    //写一个权重挑选函数
    for(i=n+1;i<=m;++i){
        int S1,S2;
        Selection(HT,i-1,&S1,&S2);     //找到两个最小的结点，并不能找到对应的最小值的位置
        HT[i].weight=HT[S1].weight+HT[S2].weight;//此结点的权重为S1+S2的权重
        HT[S1].parent=HT[S2].parent=i;   //更新最小两个结点的双亲结点
        HT[i].character='#';
        HT[i].left=S1;
        HT[i].right=S2;   //更新孩子结点
    }
    //需要对编写的哈夫曼树进行写入文件

    write_HuffmanTree(HT,n);  //写如文件操作

    HC=(HuffmanCode) malloc((n+1)*sizeof (char*));   //给二维数组指针进行分配空间
    if(HC==NULL)printf("%s\n", strerror(errno));  //判断是否分配失败
    assert(HC!=NULL);   //断言！阻止程序进行运行下去

    char* coding=(char*) malloc(n*sizeof (char));   //分配编码空间
    if(coding==NULL)printf("%s\n", strerror(errno));  //判断是否分配失败
    assert(coding!=NULL);  //阻止程序进行运行下去

    //从叶子结点到根逆向求解出每个字符的HUFFMAN编码
    coding[n-1]='\0';  //最后一个字符为编码结束符号

    for(i=1;i<=n;i++){
        int start=n-1;  //用于coding[]的动态存储
        int thread;
        int current;
        //当i=15的时候，并不能直接找到15的结点，当i等于15的时候直接跳出这一次到下一次循环
        if (i > n) {
            continue;
        }
        for(current=i,thread=HT[i].parent;thread!=0;current=thread,thread=HT[thread].parent){
            if(HT[thread].left==current){    //若是左孩子，则编码为0
                coding[--start]='0';
            } else{
                coding[--start]='1';
            }
        }
        HC[i]=(char*) malloc((n-start)*sizeof (char)); //为第i个字符编码分配空间，刚好可以分配出需要的编码空间
        strcpy(HC[i],&coding[start]);  //将字符串拷贝
    }

    write_CodeFile(HC,n);  //编码进去

    Transform_Coding(HT,n);

    free(coding);  //释放原来的空间
    free(HC);
    HC=NULL;
    HT=NULL;
}   //创建哈夫曼树，并且编码哈夫曼树

//编辑译码函数，针对上面的HC[]，我们需要将编码与HC[]对应起来，看是第几个，找出其中的i，然后打印对应的HT[i]
//涉及到子串的问题
void Transform_Coding(HuffmanTree HT,int n){
    FILE* pf_read= fopen("CodeFile.txt","r");
    FILE* pf_write= fopen("TextFile.txt","w");
    if(pf_read==NULL||pf_write==NULL){
        printf("%s\n", strerror(errno));
        assert(pf_write!=NULL);
        assert(pf_read!=NULL);
    }
    char buffer[100];  //存储从文件读取的二进制码
    fgets(buffer, sizeof(buffer),pf_read);//读到文件
    int current=2*n-1;  //直接指向根结点
    int i=0;
    while (buffer[i]!='\0'){  //直到当前二进制字符串结束，跳出循环，译码结束
        if(buffer[i]=='0'){
            current=HT[current].left;  //左子树移动，根据之前编码的情况进行选择
        } else if(buffer[i]=='1'){
            current=HT[current].right;  //右子树移动
        }
        if(HT[current].left==0&&HT[current].right==0){   //孩子结点都为0.说明已经走到叶子结点
            fprintf(pf_write, "%c ", HT[current].character);
            current=2*n-1;   //重置根结点，以便继续解码
        }
        i++;
    }
    fclose(pf_read);  //关闭文件
    fclose(pf_write);
    pf_write=NULL;  //置为NULL
    pf_read=NULL;
}





